package com.leetcode.sort;

/**
 * @author Dennis Li
 * @date 2020/7/24 22:00
 */
public class KthElement_215 {

    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            // 得到的切分点左右两边可能无序
            // 但左边的一定比切分点小、右边的一定比切分点大
            int p = partition(nums, lo, hi);
            if (p == k) {
                break;
            } else if (hi < k) {
                lo = p + 1;
            } else {
                hi = p - 1;
            }
        }
        return nums[k];
    }

    public int partition(int[] nums, int lo, int hi) {
        int i = lo + 1, j = hi;
        int p = lo;
        while (true) {
            while (i <= hi && nums[i++] < nums[p]) ;
            while (j > lo && nums[j--] > nums[p]) ;
            if (i >= j) break;
            swap(nums, i, j);
        }
        swap(nums, p, j);
        return j;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
